package Leetcode.动态规划;

import java.util.Arrays;

/**
 * @ClassName n个骰子的点数
 * @since: 2023/7/24 20:24
 * @auth: kirito
 * @description:
 **/
public class n个骰子的点数 {
    public double[] dicesProbability(int n) {
        // 点数和的范围是从n到6n
        int maxSum = 6 * n;

        // 使用两个数组轮流记录点数和为i的次数，dp[i]表示轮到当前骰子时点数和为i的次数
        int[] dp1 = new int[maxSum + 1];
        int[] dp2 = new int[maxSum + 1];

        // 初始化当只有1个骰子时的情况
        for (int i = 1; i <= 6; i++) {
            dp1[i] = 1;
        }

        // 从第2个骰子开始逐个计算点数和为i的次数
        for (int i = 2; i <= n; i++) {
            for (int j = i; j <= maxSum; j++) {
                dp2[j] = 0; // 清零当前dp2[j]
                for (int k = 1; k <= 6; k++) {
                    if (j - k < i - 1) {
                        break;  // 点数和不够i-1个骰子的情况，直接跳出循环
                    }
                    dp2[j] += dp1[j - k]; // 累加之前的次数
                }
            }
            // 将dp2的结果复制到dp1，进行下一次循环
            int[] temp = dp1;
            dp1 = dp2;
            dp2 = temp;
        }

        // 计算总次数
        double total = Math.pow(6, n);

        // 计算概率分布
        double[] probabilities = new double[maxSum - n + 1];
        for (int i = n; i <= maxSum; i++) {
            probabilities[i - n] = dp1[i] / total;
        }

        return probabilities;
    }

    public double[] dicesProbability2(int n) {
        double[] dp = new double[6];
        Arrays.fill(dp, 1.0 / 6.0);
        for (int i = 2; i <= n; i++) {
            double[] tmp = new double[5 * i + 1];
            for (int j = 0; j < dp.length; j++) {
                for (int k = 0; k < 6; k++) {
                    tmp[j + k] += dp[j] / 6.0;
                }
            }
            dp = tmp;
        }
        return dp;
    }

}
